package LeetCode;

import java.util.Random;

public class LC_382_LinkedListRandomNode {

    public static void main(String[] args) {

    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public class Solution {
        private ListNode head;
        private Random random;

        public Solution(ListNode head) {
            this.head = head;
            this.random = new Random();
        }

        public int getRandom() {
            int ans = 0;
            ListNode p = head;
            for (int cnt = 1; p != null; cnt++, p = p.next) if (random.nextInt(cnt) == 0) ans = p.val;
            return ans;
        }
    }
}